package test;


import java.util.LinkedList;
import java.util.Stack;

public class Main1 {
    /**
     * 分别按照二叉树先序，中序和后序打印所有的节点。
     *
     * @param root
     * @return
     */
    public int[][] threeOrders(TreeNode root) {
        // write code here
        int nodeCount = nodeCount(root);
        int[][] result = new int[3][nodeCount];
        preOrder(root, result[0]);
        inOrder(root, result[1]);
        postOrder(root, result[2]);
        return result;
    }


    private int nodeCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int count = 0;
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            count++;
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }
        }
        return count;
    }


    public void preOrder(TreeNode root, int[] result) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        int index = 0;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                result[index++] = cur.val;
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode temp = stack.pop();
                cur = temp.right;
            }
        }
    }

    public void inOrder(TreeNode root, int[] result) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        int index = 0;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode temp = stack.pop();
                result[index++] = temp.val;
                cur = temp.right;
            }
        }
    }

    public void postOrder(TreeNode root, int[] result) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur, pre = null;
        stack.push(root);
        int index = 0;
        while (!stack.isEmpty()) {
            cur = stack.peek();
            if (cur.left == null && cur.right == null || (pre != null && (cur.left == pre || cur.right == pre))) {
                stack.pop();
                result[index++] = cur.val;
                pre = cur;
            } else {
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            }
        }
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }
}
